class code2 {
    //方法二
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        int left = 0;
        int right = m*n -1;

        while(left <right) {
            int mid = (right-left)/2+left;
            int x = matrix[mid/n][mid%n];

            if(x > target) {
                right = mid-1;
            } else if(x < target){
                left = mid +1;
            } else {
                return true;
            }
        }
        //二分最后都要验证left和right重合的节点
        return matrix[left/n][left%n] == target;
    }
}